package 学习计划.算法基础;

/**
 * 动态规划
 */
public class Study14 {

    public static void main(String[] args) {

    }

    //413. 等差数列划分
    //如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
    //例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
    //给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
    //子数组 是数组中的一个连续序列。

    /**
     * 动态规划
     * 1，子问题：
     * 以 i 结尾的子序列最长等差数列长度为多少
     * dp[i] 贡献的等差数组个数为 dp[i]-2
     */
    public int numberOfArithmeticSlices(int[] nums) {
        int count = 0;
        int[] dp = new int[nums.length];

        for (int i = 2; i < dp.length; i++) {

            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {

                dp[i] = Math.max(dp[i - 1] + 1, 3);

                count += dp[i] - 2;
            }
        }
        return count;
    }

}
